/* 
  1 实现一个最大堆
  2 堆的两个性质
    1 堆时一个完全二叉树，即只有最后一层的元素才有可能是不满的，其他层都是满的
    2 堆中的节点一定大于其左右孩子的值
*/

class MaxHeap {
  constructor(arr, compare) {
    this.compare = compare || ((a, b) => a - b);
    // 使用一个数组存值
    if (arr) {
      this.heapify(arr);
    } else {
      this.arr = [];
    }
  }

  getSize() {
    return this.arr.length;
  }

  isEmpty() {
    return this.getSize() === 0;
  }

  parent(index) {
    return Math.floor((index - 1) / 2);
  }
  leftChild(index) {
    return Math.floor(index * 2 + 1);
  }
  rightChild(index) {
    return Math.floor(index * 2 + 2);
  }
  swap(i, j) {
    const temp = this.arr[i];
    this.arr[i] = this.arr[j];
    this.arr[j] = temp;
  }
  // 添加一个元素
  add(data) {
    this.arr.push(data);
    this.siftUp(this.arr.length - 1);
  }
  siftUp(k) {
    while (k > 0 && this.compare(this.arr[k], this.arr[this.parent(k)]) > 0) {
      // 大于父节点的值，上浮
      this.swap(k, this.parent(k));
      k = this.parent(k);
    }
  }

  findMax() {
    if (this.getSize() === 0) {
      throw new Error('heap is empty!');
    }
    return this.arr[0];
  }

  getMax() {
    const max = this.findMax();
    this.swap(0, this.getSize() - 1);
    this.arr.pop();
    this.siftDown(0);
    return max;
  }
  siftDown(k) {
    while (k < this.getSize() && this.leftChild(k) < this.getSize()) {
      let j = this.leftChild(k);
      if (
        j + 1 < this.getSize() &&
        this.compare(this.arr[j + 1], this.arr[j]) > 0
      ) {
        j = this.rightChild(k);
      }
      if (this.compare(this.arr[k], this.arr[j]) >= 0) {
        break;
      }
      this.swap(k, j);
      k = j;
    }
  }

  // 返回堆顶元素(也就是最大元素)，在插入一个新的元素
  replace(data) {
    const res = this.findMax();
    this.arr[0] = data;
    this.siftDown(0);
    return res;
  }

  // heapify（堆化，也就是给定一个数组，把它变成一个最大堆的形式）
  heapify(arr) {
    // 原理：
    /*
      分析可以发现：
        1 堆的叶子节点是不需要排序的，也就是siftDown操作
        2 只有堆的非叶子节点需要siftDown操作
      总结：从堆中的倒数第一个非叶子节点逆序开始siftDown操作，即可完成堆化 
      最后一个非叶子节点的索引就是：最后一个叶子节点的父节点
     */
    if (!arr || arr.length <= 1) {
      return;
    }
    for (let i = this.parent(arr.length - 1); i >= 0; i--) {
      this.siftDown(i);
    }
  }
}
